package interview.algorithms.bits;

/**
 * @author fance
 * @date 2018/5/16 10:51
 */
public class Solution {

    /**
     * 是否为2的n次方
     * @param n
     * @return
     */
    public boolean isPower(int n) {
        return Integer.bitCount(n) == 1;
       // return n & (n - 1) == 0;
    }

    /**
     * 二进制1的个数
     * @param n
     * @return
     */
    public int cntOne(int n) {
        // return Integer.bitCount(n);

        int cnt = 0;
        while (n > 0) {
            cnt++;
            n = n & (n - 1);
        }
        return cnt;
    }


    /**
     * 一个数字出现一次，其他两次
     * @param a
     * @return
     */
    public int oddTimesNumI(int[] a) {
        int e0 = 0;
        for (int cur : a) {
            e0 ^= cur;
        }
        return e0;
    }
    public int[] oddTimesNumII(int[] a) {
        int e0 = 0,e0hasOne = 0;
        for (int cur : a) {
            e0 ^= cur;
        }
        int rightOne = e0 & (~e0 + 1);
        for (int cur : a) {
            if ((cur & rightOne) != 0) {
                e0hasOne ^= cur;
            }
        }
        int[] res = new int[2];
        res[0] = e0hasOne;
        res[1] = e0hasOne ^ e0;
        return res;
    }

    /**
     * 其他都出现k次，求一次的数字
     * @param a
     * @param k
     * @return
     */
    public int onceNum(int[] a,int k) {
        int[] e0 = new int[32];
        for (int i = 0; i < a.length; i++) {
            setExclusiveOr(e0,a[i],k);
        }
        int res = getNumFromKSysNum(e0,k);
        return res;
    }
    private void setExclusiveOr(int[] e0,int val,int k) {
        int[] curKSysNum = getKSysNumFromNum(val,k);
        for (int i = 0; i < e0.length; i++) {
            e0[i] = (e0[i] + curKSysNum[i]) % k;
        }
    }
    private int[] getKSysNumFromNum(int val, int k) {
        int[] res = new int[32];
        int index = 0;
        while (val != 0) {
            res[index++] = val % k;
            val = val / k;
        }
        return res;
    }
    private int getNumFromKSysNum(int[] e0,int k) {
        int res = 0;
        for (int i = e0.length - 1; i >= 0; i--) {
            res = res * k + e0[i];
        }
        return res;
    }

}
